package com.zhaowei.datastruct.chapter5;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.List;
import java.util.Map;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.TreeMap;
import java.util.HashMap;
import java.util.Queue;

/*
DISTRIBUTION OF DICTIONARY:
Read the words...88984
1       1
2       48
3       601
4       2409
5       4882
6       8205
7       11989
8       13672
9       13014
10      11297
11      8617
12      6003
13      3814
14      2173
15      1169
16      600
17      302
18      107
19      53
20      28
Elapsed time FAST: 2.8 vs 3.8
Elapsed time MEDIUM: 50.9 vs 50.5
Elapsed time SLOW: 95.9 vs 96.1 (H vs T)
**/

/**
 * Word Ladder Program and Word Changing Utilities
 *
 * 文字梯子程序和文字转换工具
 */
public class WordLadder {
    public static List<String> readWords(BufferedReader in) throws IOException {
        String oneLine;
        List<String> lst = new ArrayList<>();

        while ((oneLine = in.readLine()) != null)
            lst.add(oneLine);

        return lst;
    }

    // Returns true is word1 and word2 are the same length
    // and differ in only one character.
    private static boolean oneCharOff(String word1, String word2) {
        if (word1.length() != word2.length())
            return false;

        int diffs = 0;

        for (int i = 0; i < word1.length(); i++)
            if (word1.charAt(i) != word2.charAt(i))
                if (++diffs > 1)
                    return false;

        return diffs == 1;
    }

    private static <KeyType> void update(Map<KeyType, List<String>> m, KeyType key, String value) {
        List<String> lst = m.get(key);
        if (lst == null) {
            lst = new ArrayList<>();
            m.put(key, lst);
        }

        lst.add(value);
    }

    // Computes a map in which the keys are words and values are Lists of words
    // that differ in only one character from the corresponding key.
    // Uses a quadratic algorithm (with appropriate Map).
    public static Map<String, List<String>> computeAdjacentWordsSlow(List<String> theWords) {
        Map<String, List<String>> adjWords = new HashMap<>();

        String[] words = new String[theWords.size()];

        theWords.toArray(words);
        for (int i = 0; i < words.length; i++)
            for (int j = i + 1; j < words.length; j++)
                if (oneCharOff(words[i], words[j])) {
                    update(adjWords, words[i], words[j]);
                    update(adjWords, words[j], words[i]);
                }

        return adjWords;
    }

    // Computes a map in which the keys are words and values are Lists of words
    // that differ in only one character from the corresponding key.
    // Uses a quadratic algorithm (with appropriate Map), but speeds things up a little by
    // maintaining an additional map that groups words by their length.
    public static Map<String, List<String>> computeAdjacentWordsMedium(List<String> theWords) {
        Map<String, List<String>> adjWords = new HashMap<>();
        Map<Integer, List<String>> wordsByLength = new HashMap<>();

        // Group the words by their length
        for (String w : theWords)
            update(wordsByLength, w.length(), w);

        // Work on each group separately
        for (List<String> groupsWords : wordsByLength.values()) {
            String[] words = new String[groupsWords.size()];

            groupsWords.toArray(words);
            for (int i = 0; i < words.length; i++)
                for (int j = i + 1; j < words.length; j++)
                    if (oneCharOff(words[i], words[j])) {
                        update(adjWords, words[i], words[j]);
                        update(adjWords, words[j], words[i]);
                    }
        }

        return adjWords;
    }


    // Computes a map in which the keys are words and values are Lists of words
    // that differ in only one character from the corresponding key.
    // Uses an efficient algorithm that is O(N log N) with a TreeMap, or
    // O(N) if a HashMap is used.
    public static Map<String, List<String>> computeAdjacentWords(List<String> words) {
        Map<String, List<String>> adjWords = new TreeMap<>();
        Map<Integer, List<String>> wordsByLength = new TreeMap<>();

        // Group the words by their length
        for (String w : words)
            update(wordsByLength, w.length(), w);

        // Work on each group separately
        for (Map.Entry<Integer, List<String>> entry : wordsByLength.entrySet()) {
            List<String> groupsWords = entry.getValue();
            int groupNum = entry.getKey();

            // Work on each position in each group
            for (int i = 0; i < groupNum; i++) {
                // Remove one character in specified position, computing representative.
                // Words with same representative are adjacent, so first populate
                // a map
                Map<String, List<String>> repToWord = new HashMap<>();

                for (String str : groupsWords) {
                    String rep = str.substring(0, i) + str.substring(i + 1);
                    update(repToWord, rep, str);
                }

                // and then look for map values with more than one string
                for (List<String> wordClique : repToWord.values())
                    if (wordClique.size() >= 2)
                        for (String s1 : wordClique)
                            for (String s2 : wordClique)
                                if (s1 != s2)  // must be same string; equals not needed
                                    update(adjWords, s1, s2);
            }
        }

        return adjWords;
    }

    // Find most changeable word: the word that differs in only one
    // character with the most words. Return a list of these words, in case of a tie.
    public static List<String> findMostChangeable(Map<String, List<String>> adjacentWords) {
        List<String> mostChangeableWords = new ArrayList<>();
        int maxNumberOfAdjacentWords = 0;

        for (Map.Entry<String, List<String>> entry : adjacentWords.entrySet()) {
            List<String> changes = entry.getValue();

            if (changes.size() > maxNumberOfAdjacentWords) {
                maxNumberOfAdjacentWords = changes.size();
                mostChangeableWords.clear();
            }
            if (changes.size() == maxNumberOfAdjacentWords)
                mostChangeableWords.add(entry.getKey());
        }

        return mostChangeableWords;
    }

    public static void printMostChangeables(List<String> mostChangeable,
                                            Map<String, List<String>> adjacentWords) {
        for (String word : mostChangeable) {
            System.out.print(word + ":");
            List<String> adjacents = adjacentWords.get(word);
            for (String str : adjacents)
                System.out.println(" " + str);
            System.out.println(" (" + adjacents.size() + " words)");
        }
    }

    public static void printHighChangeables(Map<String, List<String>> adjacentWords,
                                            int minWords) {
        for (Map.Entry<String, List<String>> entry : adjacentWords.entrySet()) {
            List<String> words = entry.getValue();

            if (words.size() >= minWords) {
                System.out.print(entry.getKey() + " )" + words.size() + "):");
                for (String w : words)
                    System.out.print(" " + w);
                System.out.println();
            }
        }
    }

    // After the shortest path calculation has run, computes the List that
    // contains the sequence of word changes to get from first to second.
    public static List<String> getChainFromPreviousMap(Map<String, String> prev,
                                                       String first, String second) {
        LinkedList<String> result = new LinkedList<>();

        if (prev.get(second) != null)
            for (String str = second; str != null; str = prev.get(str))
                result.addFirst(str);

        return result;
    }

    // Runs the shortest path calculation from the adjacency map, returning a List
    // that contains the sequence of words changes to get from first to second.
    public static List<String> findChain(Map<String, List<String>> adjacentWords, String first, String second) {
        Map<String, String> previousWord = new HashMap<>();
        Queue<String> q = new LinkedList<>();

        q.add(first);
        while (!q.isEmpty()) {
            String current = q.element();
            q.remove();
            List<String> adj = adjacentWords.get(current);

            if (adj != null)
                for (String adjWord : adj)
                    if (previousWord.get(adjWord) == null) {
                        previousWord.put(adjWord, current);
                        q.add(adjWord);
                    }
        }

        previousWord.put(first, null);

        return getChainFromPreviousMap(previousWord, first, second);
    }

    // Runs the shortest path calculation from the original list of words, returning
    // a List that contains the sequence of word changes to get from first to
    // second. Since this calls computeAdjacentWords, it is recommended that the
    // user instead call computeAdjacentWords once and then call other findChar for
    // each word pair.
    public static List<String> findChain(List<String> words, String first, String second) {
        Map<String, List<String>> adjacentWords = computeAdjacentWords(words);
        return findChain(adjacentWords, first, second);
    }

    public static void main(String[] args) throws IOException {
        long start, end;

        FileReader fin = new FileReader("dict.txt");
        BufferedReader bin = new BufferedReader(fin);
        List<String> words = readWords(bin);
        System.out.println("Read the words..." + words.size());
        Map<String, List<String>> adjacentWords;

        start = System.currentTimeMillis();
        adjacentWords = computeAdjacentWords(words);
        end = System.currentTimeMillis();
        System.out.println("Elapsed time FAST: " + (end - start));

        start = System.currentTimeMillis();
        adjacentWords = computeAdjacentWordsMedium(words);
        end = System.currentTimeMillis();
        System.out.println("Elapsed time MEDIUM: " + (end - start));


        start = System.currentTimeMillis();
        adjacentWords = computeAdjacentWordsSlow(words);
        end = System.currentTimeMillis();
        System.out.println("Elapsed time SLOW: " + (end - start));


        // printHighChangeables( adjacentWords, 15 );

        System.out.println("Adjacents computed...");
        List<String> mostChangeable = findMostChangeable(adjacentWords);
        System.out.println("Most changeable computed...");
        printMostChangeables(mostChangeable, adjacentWords);

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        for (; ; ) {
            System.out.println("Enter two words: ");
            String w1 = in.readLine();
            String w2 = in.readLine();

            List<String> path = findChain(adjacentWords, w1, w2);
            System.out.print(path.size() + "...");
            for (String word : path)
                System.out.print(" " + word);
            System.out.println();
        }
    }
}
